/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/yang-hui-triangle
   @Language: C++
   @Datetime: 19-04-22 09:56
   */

class Solution {
public:
	/**
	 * @param n: a Integer
	 * @return: the first n-line Yang Hui's triangle
	 */
	vector<vector<int>> calcYangHuisTriangle(int n) {
		// write your code here
		vector<vector<int> > vs;
		for(int i=0; i<n; ++i){
			vector<int> v(i+1,1);
			for(int j=1; j<i; ++j)
				v[j]=vs[i-1][j-1]+vs[i-1][j];
			vs.push_back(v);
		}
		return vs;
	}
};
